package com.zyk.grate_offer.class04;

/**
 * 返回一个数组中，子数组最大累加和
 *
 * @author zhangsan
 * @date 2021/4/28 15:54
 */
public class Code02_MaxSumInSubArray {

    public static int maxSum(int[] nums) {
        int ans = nums[0];
        int sum = 0;
        for (int num : nums) {
            if (sum > 0) {
                sum += num;
            } else {
                sum = num;
            }
            ans = Math.max(ans, sum);
        }
        return ans;
    }

    // 数组最大累加和. 转换一下问题描述即: 以i结尾最大累加和是多少?
    // 然后可以转移为:
    // 1. 要i-1的结果和他加起来
    // 2. 不要i-1的结果
    // 求最大值就是以i结束的最大累加和
    // 因为所有元素只依赖于i-1项, 所以一个变量即可搞定
    public static int maxSum2(int[] nums) {
        int ans = nums[0], pre = ans;
        for (int i = 1; i < nums.length; i++)
            ans = Math.max(ans, (pre = Math.max(nums[i], pre + nums[i])));
        return ans;
    }


    // for test
    public static void main(String[] args) {
        /*int[] arr = {-1, 3, -6, 7, -4, 1, -7, 9};
        System.out.println(maxSum(arr));
        System.out.println(maxSum2(arr));*/


        int times = 100000,
            maxLen = 1000,
            maxVal = 40;
        System.out.println("test begin.");
        for (int i = 0; i < times; i++) {
            int[] arr = generateArray(maxLen, maxVal);
            int ans1 = maxSum(arr);
            int ans2 = maxSum2(arr);
            if(ans1 != ans2) {
                System.out.println("OOPS!");
                break;
            }
        }
        System.out.println("test end!");
    }

    // for test
    public static int[] generateArray(int maxLen, int maxVal) {
        maxLen = (int) (Math.random() * maxLen) + 1;
        int[] res = new int[maxLen];
        for (int i = 0; i < maxLen; i++) {
            res[i] = (int) (Math.random() * maxVal - Math.random() * maxVal);
        }
        return res;
    }

}
